// #define print(...)

#define DP(i,j) ( (i)>(j) ? dp[(1+(i))*(i)/2+(j)] : dp[(1+(j))*(j)/2+(i)] )

class Solution {
public:
    string longestPalindrome(string s) {
        auto N = s.size();
        if(N < 2) return s;
        vector<bool> dp((1+N)*N/2, false);
        // 单字符是回文串
        for(int i=0; i<N; i++)
            DP(i,i) = true;
        // 找最大
        int maxlen = 1, begin = 0;
        for(int len=2; len<=N; len++){
            for(int i=0,j=i+len-1; i<N&&j<N; ++i,j=i+len-1){// j-i+1=len
                if(s[i] == s[j]){
                    if(len<=3) DP(i,j) = true;
                    else DP(i,j) = DP(i+1, j-1);
                } else {
                    DP(i,j) = false;
                }
                if(DP(i,j) && len>maxlen){
                    maxlen = len;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxlen);
    }
};
